Search results for "Difference set"

Binary Patterns in Infinite Binary Words

2002

In this paper we study the set P(w) of binary patterns that can occur in one infinite binary word w, comparing it with the set F(w) of factors of the word. Since the set P(w) can be considered as an extension of the set F(w), we first investigate how large is such extension, by introducing the parameter ?(w) that corresponds to the cardinality of the difference set P(w) \ F(w). Some non trivial results about such parameter are obtained in the case of the Thue-Morse and the Fibonacci words. Since, in most cases, the parameter ?(w) is infinite, we introduce the pattern complexity of w, which corresponds to the complexity of the language P(w). As a main result, we prove that there exist infini…